package com.gxc.array;

import java.util.Arrays;

/**
 * 16. 最接近的三数之和
 * 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。
 * 请你从 nums 中选出三个整数，使它们的和与 target 最接近。
 *
 * 返回这三个数的和。
 *
 * 假定每组输入只存在恰好一个解。
 */
public class ThreeSumClosest {

    public static void main(String[] args) {
        int[] nums = new int[]{-1, 2, 1, -4};
        int target = 1;
        System.out.println(handle(nums, target));
    }

    /**
     * 暴力三层循环
     * @param nums
     * @param target
     * @return
     */
    private static int handle(int[] nums, int target) {
        int min = Integer.MAX_VALUE;
        int closet = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                for (int k = j+1; k < nums.length; k++) {
                    int sum = nums[i] + nums[j] + nums[k];
                    if (Math.abs(target - sum) < min) {
                        min = Math.abs(target - sum);
                        closet = sum;
                    }
                }
            }
        }
        return closet;
    }

    // 先排序 再双指针  双指针代替双循环
    private static int handle2(int[] nums, int target) {
        //先排序
        Arrays.sort(nums);

        int n = nums.length;
        int min = Integer.MAX_VALUE;
        int closet = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;
        for (int i = 0; i < nums.length; i++) {
           left = i+1;
           right = n-1;
           while (left < right) {
               int sum = nums[i] + nums[left] + nums[right];
               //如果和比目标值小，则需要增大和，则需要左指针右移
               if (sum == target) {
                   return sum;
               } else if (sum<target) {
                   while (left<right && nums[left] == nums[left+1]) {
                       left++;
                   }
                   left++;
               } else {
                   while (right>left && nums[right] == nums[right-1]) {
                       right--;
                   }
                   right--;
               }
               if (Math.abs(target - sum) < min) {
                   min = Math.abs(target - sum);
                   closet = sum;
               }
           }
        }
        return closet;
    }
}
